Date: Tue, 14 Jan 1997 22:51:25 GMT
Server: Apache/1.1b4
Content-type: text/html
Content-length: 18556
Last-modified: Sat, 21 Dec 1996 00:20:04 GMT

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML Strict Level 2//EN">
<html>
  <head>
    <title>CptSci 112a: Lecture schedule</title>
    <link href="mailto:aspnes@cs.yale.edu" rev="MADE"></head>
  <body>
    <h1>CptSci 112a: Lecture schedule</h1>

    <p><!WA0><a href="http://pine.cs.yale.edu:4201/cs112/index.html">Return to the CptSci 112a home page.</a></p>

    <h2><a name="previous"></a>Previous lectures and events.</h2>

    <dl>
      <dt>12/20/96, at 2:00pm, in WLH 116</dt>
      <dd><strong>Final Exam</strong>.  The final will be a
        cumulative closed-book exam.  Just like the midterm, but half
        again
        as long.  A <!WA1><a href="http://pine.cs.yale.edu:4201/cs112/sample-final.html">sample final</a> (with
        <!WA2><a href="http://pine.cs.yale.edu:4201/cs112/sample-final-solutions.html">solutions</a>) is
      available.</dd>

      <dt>12/12/96, 7:00pm, in AKW 500</dt>
      <dd>Review session.</dd>

      <dt>12/6/96</dt>
      <dd>Retrospective.  Where to go from here.</dd>

      <dt>12/4/96</dt>
      <dd>Binary trees.</dd>

      <dt>12/2/96</dt>
      <dd>Recursive search procedures.</dd>

      <dt>11/22/96</dt>
      <dd>More examples of divide-and-conquer.  Algorithms and their
        worst-case costs.  Binary search and mergesort.<dl>
          <dt><!WA3><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.22/">Demos:</a></dt>
          <dd><ul>
              <li><!WA4><a
      href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.22/mergesort.p">mergesort.p</a>  Unlike
      the demo in lecture, this program actually works.</li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>11/20/96</dt>
      <dd>Recursion.  Divide-and-conquer as a tool for solving
      problems.  Finding all combinations and permutations of letters in a
        string.<dl>
          <dt>Readings:</dt>
          <dd>Chapter 16.</dd>
        </dl>
      </dd>

      <dt>11/18/96</dt>
      <dd>Queues.
        <dl>
          <dt>Readings:</dt>
          <dd>Sections 15.2-15.3.</dd>
          <dt><!WA5><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.18/">Demos:</a></dt>
          <dd><ul>
              <li><!WA6><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.18/queue.p">queue.p</a></li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>11/15/96</dt>
      <dd>Abstract data types.  Concrete representations vs
        abstractions.  Dictionaries and stacks.<dl>
          <dt>Readings:</dt>
          <dd>Sections 15.1, 15.4-15.6</dd>
        </dl>
</dd>

      <dt>11/13/96</dt>
      <dd>Hash tables.  A hash table is a trick for speeding up access
      to the elements of a linked list by splitting the list into many
      separate lists (stored in an array).  To find out which list
        each element goes in, one uses a <em>hash function</em> that
      transforms each element into a consistent but random-looking
      number.  The effect is a bit like using a filing cabinet with
      many separate folders to store data instead of one big stack of
        paper.  See the demo program for an example.<dl>
          <dt><!WA7><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.13/">Demos:</a></dt>
          <dd><ul>
              <li><!WA8><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.13/hashtable.p">hashtable.p</a></li>
            </ul>
          </dd></dl>
</dd>

      <dt>11/11/96</dt>
      <dd>Linked lists.  Traversal, insertion, deletion.<dl>
          <dt><!WA9><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.11/">Demos:</a></dt>
          <dd><ul>
              <li><!WA10><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.11/linkedLists.p">linkedLists.p</a></li>
            </ul>
          </dd>
          <dt>Readings:</dt>
          <dd>Sections 14.12-14.16</dd>
        </dl>
      </dd>

      <dt>11/8/96</dt>
      <dd>Pointer basics.  Declaring pointer variables.  Operations on
        pointers.  <tt>New</tt> and <tt>Dispose</tt>.  Declaring and
        adding elements to a linked list.<dl>
          <dt>Readings:</dt>
          <dd>Sections 14.1-14.11.</dd>
        </dl>
      </dd>

      <dt>11/6/96</dt>
      <dd>More file munching.  Using files to communicate between
        different programs.<dl>
          <dt><!WA11><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/">Demos:</a></dt>
          <dd><ul>
              <li><!WA12><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/draw.p">draw.p</a>.
      Drawing program that saves its work to a file.</li>
              <li><!WA13><a
      href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/redraw.p">redraw.p</a>.  Displays files
                in the format generated by draw.p.</li>
              <li><!WA14><a
      href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/autodraw.p">autodraw.p</a>.  Generates
      a file suitable for loading in redraw.p.</li>
              <li><!WA15><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/circle">circle</a>.
      Output of autodraw.p.</li>
              <li><!WA16><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/monet">monet</a>.  A
      formerly huge drawing of a smiley-face, signed by the master.
                This is a compressed version of the <tt>test</tt> file
      drawn in class.  The compression was done on a Unix machine
                using a program written in <tt>Perl</tt>, which
      demonstrates how data files with well-defined formats can be
      manipulated by a wide variety of tools.</li>
              <li><!WA17><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.06/picasso">picasso</a>.
      Another fine work of art from class.</li>
            </ul>
          </dd>
          <dt>Handouts:</dt>
          <dd><!WA18><a href="http://pine.cs.yale.edu:4201/cs112/hw8.html">Assignment Eight.</a></dd>
        </dl>
      </dd>

      <dt>11/4/96</dt>
      <dd>Files.  Reading and Writing files.  Basic file commands:
        Reset, Rewrite, Close, NewFilename, OldFilename.<dl>
          <dt>Readings:</dt>
          <dd>Sections 9.3-9.6</dd>
          <dt><!WA19><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.04/">Demos:</a></dt>
          <dd><ul>
              <li><!WA20><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.04/cheapEdit.p">cheapEdit.p</a></li>
            </ul>
          </dd>

        </dl>
</dd>

      <dt>11/1/96</dt>
      <dd>Sets. 
        <dl>
          <dt>Readings:</dt>
          <dd>Sections 13.3-13.5.</dd>
          <dt><!WA21><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.01/">Demos:</a></dt>
          <dd><ul>
              <li><!WA22><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.11.01/sets.p">sets.p</a></li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>10/30/96</dt>
      <dd>Operations on characters.  Chr and Ord.  Parsing using
        finite-state machines.
        <dl>
          <dt>Readings:</dt>
          <dd>Section 8.1.</dd>
          <dt>Handouts:</dt>
          <dd><!WA23><a href="http://pine.cs.yale.edu:4201/cs112/hw7.html">Assignment Seven.</a></dd>
        </dl>
      </dd>

      <dt>10/28/96</dt>
      <dd>Built-in functions for manipulating strings: pos, copy,
        omit, include, and concat.<dl>
          <dt>Readings:</dt>
          <dd>Section 8.5</dd>
          <dt><!WA24><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.28/">Demos:</a></dt>
          <dd><ul>
              <li><!WA25><a
                  href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.28/replacer.p">replacer.p</a>  With bonus
                <tt>YesMaster</tt> procedure, not shown in lecture!</li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>10/25/96</dt>
      <dd>Strings and characters.  The Length function.  Treating a
        string like an array of characters.<dl>
          <dt>Readings:</dt>
          <dd>Sections 8.1-8.4, plus Length description in 8.5.</dd>
          <dt><!WA26><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.25/">Demos:</a></dt>
          <dd><ul>
              <li><!WA27><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.25/stringMauler.p">stringMauler.p</a></li>
            </ul>
          </dd>

        </dl>
      </dd>

      <dt>10/23/96</dt>
      <dd>Variant records.<dl>
          <dt>Readings:</dt>
          <dd>Sections 13.6 and 13.7.</dd>
          <dt><!WA28><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.23/">Demos:</a></dt>
          <dd><ul>
              <li><!WA29><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.23/cheapdraw.p">cheapdraw.p</a></li>
            </ul>
          </dd>
          <dt>Handouts:</dt>
          <dd><!WA30><a href="http://pine.cs.yale.edu:4201/cs112/hw6.html">Assignment Six.</a></dd>
        </dl>
      </dd>

      <dt>10/21/96</dt>
      <dd>Enumerated data types.<dl>
          <dt>Readings:</dt>
          <dd>Sections 13.1 and 13.2.</dd>
          <dt><!WA31><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.21/">Demos:</a></dt>
          <dd><ul>
              <li><!WA32><a
      href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.21/conquest.p">conquest.p</a>  This
      program didn't appear at all in lecture, but I wrote it
      beforehand while playing around with enumerated data types, and
      it has some nice examples of doing things with them and 2-d
      arrays.  So I figured it would make more sense to put it up here
      than let it go to waste.</li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>10/18/96</dt>
      <dd>Multi-dimensional arrays and their uses.<dl>
          <dt>Readings:</dt>
          <dd>Section 11.9.  Ignore the discussion in Section 11.8 on
            parallel arrays.  The technique
            discussed there is almost always better done with an array
            of records as described in Section 12.2.</dd>
          <dt><!WA33><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.18/">Demos:</a></dt>
          <dd><ul>
              <li><!WA34><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.18/toxic.p">toxic.p</a>
      (This version is slightly improved from the one shown in
      lecture; it includes a version of ButtonClick that works
      better.)</li>
            </ul>
          </dd>

        </dl>
      </dd>

      <dt><a name="midterm"></a>10/16/96</dt>
      <dd><strong>Midterm.</strong> The midterm will be give in class
        at the usual time and location.  It will be a closed-book
        test, covering everything discussed in class up to 10/11/96.
        You should be comfortable with the material in Chapters 1, 2, 3
        (Sections 3.1-3.4 only), 4, 5, 6, and Sections 11.1-11.4 and
        12.1 and 12.2 in the book.  A <!WA35><a href="http://pine.cs.yale.edu:4201/cs112/sample-midterm.html">sample
          midterm</a> is available showing roughly the length and types
        of questions you should expect; you may wish to try going through
      this before the review session to see if you have any
      questions.  Note that questions on the sample midterm are not
      exhaustive: the real midterm may touch on different subjects and
      use different types of questions.
        <dl>
          <dt>Handouts:</dt>
          <dd><!WA36><a href="http://pine.cs.yale.edu:4201/cs112/hw5.html">Assignment Five.</a></dd>
        </dl>
      </dd>


      <dt>10/14/96</dt>
      <dd>Review session.</dd>

      <dt>10/11/96</dt>
      <dd>More tricks with arrays.  Computing minima and maxima,
        searching, sorting.<dl>
          <dt>Readings:</dt>
          <dd>Sections 11.6, 11.7.</dd>
          <dt><!WA37><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.11/">Demos:</a></dt>
          <dd><ul>
              <li><!WA38><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.11/arrayMauler.p">arrayMauler.p</a></li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>10/9/96</dt>
      <dd>Arrays.<dl>
          <dt>Readings:</dt>
          <dd>Sections 11.1-11.4, 12.2.</dd>
          <dt><!WA39><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.09/">Demos:</a></dt>
          <dd><ul>
              <li><!WA40><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.09/arrayExample.p">arrayExample.p</a></li>
            </ul>
          </dd>

        </dl>
      </dd>

      <dt>10/7/96</dt>
      <dd>Records and abstract data types.<dl>
          <dt>Readings:</dt>
          <dd>Section 12.1.  (Yes, this is skipping ahead a lot.
            We'll come back.)</dd>
          <dt><!WA41><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.07/">Demos:</a></dt>
          <dd><ul>
              <li><!WA42><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.07/abstractBall.p">abstractBall.p</a></li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>10/4/96</dt>
      <dd>Procedures with state.  Most procedures maintain no
      information from one call to the next, so they always act
      exactly the same way.  Sometimes this isn't what we want, so by
      used of a global variable or a call-by-reference parameter we
        can produce procedures like <em>iterators</em> (returning
        e.g. 1,2,3,4,5, etc.) or <em>pseudorandom number
      generators</em> (which return random-looking numbers; see also
        the <!WA43><a href="http://pine.cs.yale.edu:4201/cs112/library.html#random">library of useful
      procedures</a>).</dd>

      <dt>10/2/96</dt>
      <dd>Examples of using call-by-reference parameters and
        functions.  Getting input from the mouse.
        <dl>
          <dt><!WA44><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.02/">Demos:</a></dt>
          <dd><ul>
              <li><!WA45><a
                  href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.02/average.p">average.p</a>
                illustrates use of various techniques to return information
                from procedures.</li>
              <li><!WA46><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.02/mouse.p">mouse.p</a> A
                simple drawing program.</li>
              <li><!WA47><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.10.02/button.p">button.p</a>
                Detecting button clicks.</li>
            </ul>
          </dd>
          <dt>Handouts:</dt>
          <dd><!WA48><a href="http://pine.cs.yale.edu:4201/cs112/hw4.html">Assignment Four.</a></dd>
        </dl>
      </dd>

      <dt>9/30/96</dt>
      <dd>How Pascal uses memory.  Global variables vs local
        variables.  Call-by-reference (var) parameters.  Functions.
        <dl>
          <dt>Readings:</dt>
          <dd>Sections 6.2-6.4.</dd>
        </dl>
</dd>

      <dt>9/27/96</dt>
      <dd>Examples of using while and repeat..until loops.
        <dl>
          <dt><!WA49><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.27/">Demos:</a></dt>
          <dd><ul>
              <li><!WA50><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.27/loopdemo.p">loopdemo.p</a></li>
            </ul>
          </dd></dl>
      </dd>

      <dt>9/25/96</dt>
      <dd>More applications of loops: animation.  Unbounded loops.<dl>
          <dt>Handouts:</dt>
          <dd><!WA51><a href="http://pine.cs.yale.edu:4201/cs112/hw3.html">Assignment Three.</a></dd>
          <dt><!WA52><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.25/">Demos:</a></dt>
          <dd><ul>
              <li><!WA53><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.25/animation.p">animation.p</a></li>
            </ul>
          </dd>
          <dt>Readings:</dt>
          <dd>Sections 5.3, 5.5.</dd>
        </dl>
      </dd>

      <dt>9/23/96</dt>
      <dd>More about for loops.  Debugging.  Fencepost errors.
        <dl>
          <dt><!WA54><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.23/">Demos:</a></dt>
          <dd><ul>
              <li><!WA55><a
      href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.23/dashes.p">dashes.p</a></li>
              <li><!WA56><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.23/timestables.p">timestables.p</a></li>
            </ul>
          </dd>
        </dl>
      </dd>

      <dt>9/20/96</dt>
      <dd>Introduction to loops.  Bounded loops: for/to and
      for/downto.
        <dl>
          <dt><!WA57><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.20">Demos:</a></dt>
          <dd><ul>
              <li><!WA58><a
          href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.20/bottles.p">bottles.p</a> "99
          Bottles of Beer on the Wall" --- a simple program using a for
          loop.</li>
              <li><!WA59><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.20/circles.p">circles.p</a>.  Draws
          a bunch of circles; example of nested for loops.</li>
            </ul>
          </dd>
          <dt>Readings:</dt>
          <dd>Sections 5.1, 5.2, 5.8 (first part).</dd>
        </dl>
      </dd>

      <dt>9/18/96</dt>
      <dd>The case statement.  Local variables.
        <dl>
          <dt>Demos:</dt>
          <dd><!WA60><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.18/">personality.p</a> (Case
            statement demo).</dd>
          <dt>Handouts:</dt>
          <dd><!WA61><a href="http://pine.cs.yale.edu:4201/cs112/hw2.html">Assignment Two.</a></dd>
          <dt>Readings:</dt>
          <dd>Section 4.7 (case statement), Sections 2.3, 2.4, 6.1.</dd>
        </dl>
      </dd>

      <dt>9/16/96</dt>
      <dd>More tricks with if/then statements.  Boolean expressions
        and variables.  Preview of recursion.
        <dl>
          <dt><!WA62><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.16/">Demos:</a></dt>
          <dd>
            <ul>
              <li><!WA63><a
                  href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.16/admission.p">admission.p</a> (Yale College admissions program)</li>
              <li><!WA64><a
                  href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.16/fancyFaces.p">fancyFaces.p</a> (blinking faces)</li>
              <li><!WA65><a
                  href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.16/recursive.p">recursive.p</a> (bomb timer program using recursive procedures)</li>
            </ul>
          </dd>
          <dt>Readings:</dt>
          <dd>Sections 4.4, 4.6, 4.8.  Resist the temptation to read
            Section 4.5: the description of how to get the mouse
            position will not work in Think Pascal.</dd>
        </dl>
      </dd>

      <dt>9/13/96</dt>
      <dd>Pascal syntax and the mysteries of semicolon placement.
        Begin..end blocks.  If/then statements.
        <dl>
          <dt>Readings:</dt>
          <dd>Sections 4.1-4.3 (various forms of if/then statements).</dd>
        </dl>
      </dd> 

      <dt>9/11/96</dt> 
      <dd>More graphics.  Decomposing tasks into subtasks, and then
      building procedures to do all the subtasks.
        <dl>
          <dt>Demos:</dt>
          <dd><!WA66><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.11/">face.p</a> Draws a bunch
            of cartoon faces.</dd>
          <dt>Handouts:</dt>
          <dd><!WA67><a href="http://pine.cs.yale.edu:4201/cs112/hw1.html">Homework One</a></dd>
          <dt>Readings:</dt>
          <dd>Sections 3.1-3.4, 3.10 (basic graphics commands).</dd>
        </dl></dd>

      <dt>9/9/96</dt>
      <dd>Arithmetic.  Integers vs reals.  Graphics commands.<dl>
          <dt>Demos:</dt>
          <dd><!WA68><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.09/">drawing.p</a> (Basic
            drawing commands).</dd>
          <dt>Readings:</dt>
          <dd>Sections 2.1-2.3, 2.5 (arithmetic); 2.7-2.8 (drawing
            lines).</dd>
        </dl>
      </dd>

      <dt>9/6/96</dt>
      <dd>Declaring and using constants and procedures.  How avoiding
        redundancy increases clarity and power of programs.
        <dl>
          <dt>Demos:</dt>
          <dd><!WA69><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.06/">Old MacDonald program.</a></dd>
          <dt>Handouts:</dt>
          <dd><!WA70><a href="http://pine.cs.yale.edu:4201/cs112/howto.html">HOW TO sheet.</a></dd>
          <dt>Readings:</dt>
          <dd>Sections 1.8 (simple procedures), 2.12 (constants), 6.1
            (procedures with parameters). You should probably also
            read Sections 2.10 and 2.11 (input and output).</dd>
        </dl>
      </dd>

      <dt>9/4/96</dt> 
      <dd>Introduction.  How the course is set up.
        What programming is all about.  Running Think Pascal.
        <dl>
          <dt>Demos:</dt>
          <dd><!WA71><a href="http://pine.cs.yale.edu:4201/cs112/programs/1996.09.04/">boring.p</a></dd>
          <dt>Handouts:</dt>
          <dd><ul>
              <li><!WA72><a href="http://pine.cs.yale.edu:4201/cs112/syllabus.html">Course Information</a></li> 
              <li><!WA73><a href="http://pine.cs.yale.edu:4201/cs112/hw0.html">Homework Zero</a></li>
              <li>Introductory computer science courses.</li>
            </ul>
          </dd>
          <dt>Readings:</dt>
          <dd>Chapter 1.</dd>
        </dl>
      </dd>
    </dl>

<hr>
<p><!WA74><a href="http://pine.cs.yale.edu:4201/cs112/index.html">Return to the CptSci 112a home page.</a></p>
  </body>
</html>
